import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 39 数组总和
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * <p>
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
 * <p>
 * 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
 * 动态规划
 */
public class ArraySum {

    @Test
    public void test1() {
        int[] arr = new int[]{2, 3, 5};
        List<Integer> r1 = Arrays.asList(2, 2, 2, 2);
        List<Integer> r2 = Arrays.asList(2, 3, 3);
        List<Integer> r3 = Arrays.asList(3, 5);

        List<List<Integer>> result = combinationSum(arr, 8);

        Assertions.assertTrue(result.contains(r1));
        Assertions.assertTrue(result.contains(r2));
        Assertions.assertTrue(result.contains(r3));
        Assertions.assertEquals(3, result.size());
    }

    @Test
    public void test2() {
        int[] arr = new int[]{2, 3, 6, 7};

        List<Integer> r1 = Arrays.asList(7);
        List<Integer> r2 = Arrays.asList(2, 2, 3);

        List<List<Integer>> result = combinationSum(arr, 7);

        Assertions.assertTrue(result.contains(r1));
        Assertions.assertTrue(result.contains(r2));
        Assertions.assertEquals(2, result.size());
    }



    int[] candidates;

    /**
     * 要找的值映射候选值在 candidates 数组中的索引
     */
    Map<Integer, Integer> valMappingIndex = new HashMap<>();

    /**
     * 存储算法的结果
     */
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        this.candidates = candidates;
        for (int i = 0; i < candidates.length; i++) {
            valMappingIndex.put(candidates[i], i);
        }
        find(target, new ArrayList<>());

//        对结果进行排序，去重处理
        return result.stream().peek(Collections::sort).distinct().sorted((l1, l2) -> {
            return l1.iterator().next() - l2.iterator().next();
        }).collect(Collectors.toList());

    }

    void find(int target, List<Integer> previousResult) {

        Integer index = valMappingIndex.get(target);

        if (index != null) {
//          缓存命中
            int expected = candidates[index];
//          拷贝每次递归传递进来的结果
            ArrayList<Integer> r = new ArrayList<>(previousResult);
//          加入此次命中的结果
            r.add(expected);
//          放入到结果集中
            result.add(r);
        }
        for (int candidate : candidates) {

            int nextTarget = target - candidate;

            if (nextTarget <= 0) {
                return;
            }
//            拷贝预先得到的结果集
            List<Integer> previous = new ArrayList<>(previousResult);
//            将本轮的候选数字放入到集合中
            previous.add(candidate);
//            进行下一步递归
            find(nextTarget, previous);
        }

    }


}
